'''
多重背包模版
f1: 尝试+dp缓存
f: 基于f1修改的基本的多重背包解法: 时间复杂度: O(X*N*sum(C))
g: 通过二进制枚举数量c，将问题转化为01背包: 时间复杂度: O(X*N*sum(log(C)))
h: 通过余数分组，窗口维护选择数量，单调队列更新窗口最大值优化: 时间复杂度: O(X*N)
'''
from collections import deque
from functools import cache

import numpy as np


# V[i]: i物品体积
# W[i]：i物品权重/价值
# C[i]：i物品最多选C[i]个
# X: 背包容量
def f1(V, W, C, X):
    n = len(V)

    # i: 第i个物品
    # rest: 背包剩余容量
    @cache
    def f(i, rest):
        if i == n:
            return 0
        res = 0
        for time in range(C[i] + 1):  # 选 0,1,2,...,C[i]个当前物品
            if rest - time * V[i] >= 0:
                res = max(res, W[i] * time + f(i + 1, rest - time * V[i]))
        return res

    return f(0, X)


# O(X*N*sum(C))
def f(V, W, C, X):
    n = len(V)
    dp = [[0] * (X + 1) for _ in range(n + 1)]
    # 第一维度依赖后边的, 第二维度依赖前边的
    for i in range(n - 1, -1, -1):
        for j in range(X + 1):
            res = 0
            # for time in range(C[i] + 1):
            for time in range(1 + min(C[i], j // V[i])):
                res = max(res, W[i] * time + dp[i + 1][j - time * V[i]])
            dp[i][j] = res
    # print(dp)
    return dp[0][X]


# O(X*N*sum(log(C)))
# 换思路了，将问题转化为01背包
# 怎么转化呢，就是将物品比如可以选50个 x物品
# 然后将它二进制划分 为： 1个的,2个的,4个的，8个的，16个的, 50-(1+2+4+8+16) = 19个的
#       1)这样不会错过答案，比如3的我们可以用1+2, 5个的可以用4+1, ... 0~50个都可以选择到
#       2)划分别忘了加价值，和体积
def g(V, W, C, X):
    n = len(V)
    V2 = []
    W2 = []
    for i in range(n):
        num = C[i]
        v, w = V[i], W[i]
        t = 1
        while num >= t:
            V2.append(v * t)
            W2.append(w * t)
            num -= t
            t <<= 1
        if num:
            V2.append(v * num)
            W2.append(w * num)

    # 然后再V2, W2, X 上做01背包
    n = len(V2)
    dp = [[0] * (X + 1) for _ in range(n + 1)]
    for i in range(n - 1, -1, -1):
        for rest in range(X + 1):
            r1 = dp[i + 1][rest]
            r2 = (dp[i + 1][rest - V2[i]] + W2[i]) if V2[i] <= rest else 0
            dp[i][rest] = max(r1, r2)
    # print(dp)
    return dp[0][X]


# O(X*N))
# 余数分组，窗口维护选择的数量，单调队列优化
# 变量，系数声明：=========================
# X: 背包容量
# v, w, c: 体积，价值，最多出现的次数
# i: 第i个选择的物品
# j：当前背包剩余的容量
# r: 余数分组：r=j%v 当前背包容量对这个物品的余数，范围[0,v)
# k: 系数：表示 j 在余数分组内的位置，即 j%v=r  =>  j = r + k*v     # k = (j-r)/v 或 k = j//v向下取整
#       k: 也可以看作是根据r分组后的组内下标，范围：[0, (X-r)//v]   j0 = r, j1 = j0 + v, j2 = j1 + v, j3 = j2+v
# t: 选择次数：表示选择当前物品的次数（取值范围 [0, c]
# 1) i是固定的v,w,c是固定的，
# 2) 根据r分组, 来选择j
# 3) k也是固定的k==j//v
# 4) 唯一的变量是t     =>     t的变化影响的是 k', j'及对后边的j来说之前的j',k'
# 数学推导状态转移方程：=========================
# 原方程 dp[i][j] = max{ dp[i+1][j - t*v] + t*w | 0 ≤ t ≤ min(c, j // v) }
#       =>      dp[i][r + k*v] = max{ dp[i+1][r + k*v - t*v] + t*w }
#       =>      dp[i][r + k*v] = max{ dp[i+1][r+(k-t)*v] - (k-t)*w + k*w }
#   t的取值范围:[0, c]，另k' = k-t, k'的取值范围为：[k-c, k]，当前窗口的大小则：
#       =>      dp[i][r + k*v] = max{ dp[i+1][r+(k')*v] - (k')*w + k*w }
#   6) k'的取值范围为：[k-c, k]        [j//v - c, j//v]
# 比如c=3, v=2, w
# dp[i][1]  = max{ dp[i+1][1]  + 0w }
# dp[i][3]  = max{ dp[i+1][3]  + 0w, dp[i+1][1] + 1w }
# dp[i][5]  = max{ dp[i+1][5]  + 0w, dp[i+1][3] + 1w, dp[i+1][1] + 2w }
# dp[i][7]  = max{ dp[i+1][7]  + 0w, dp[i+1][5] + 1w, dp[i+1][3] + 2w, dp[i+1][1] + 3w }
# dp[i][9]  = max{ dp[i+1][9]  + 0w, dp[i+1][7] + 1w, dp[i+1][5] + 2w, dp[i+1][3] + 3w }
# dp[i][11] = max{ dp[i+1][11] + 0w, dp[i+1][9] + 1w, dp[i+1][7] + 2w, dp[i+1][5] + 3w }
# ...
# 我们想要通过单调队列，来维护一个最大为c的窗口
#   note: 队列不能直接存dp[i+1][j']的值，因为对于后边的来说他的选择的数量变了
#       trick q存储k的信息-kw,比如对于11来说
#           要得到11的信息直接拿 -5w + 5w = 0w   # 有可能他是最好的结果
#           要得到9的信息直接拿 -4w + 5w = 1w
#           要得到7的信息直接拿 -3w + 5w = 2w
#           要得到5的信息直接拿 -2w + 5w = 3w
#           要得到3的信息直接拿 -1w + 5w = 4w    # 超过限制也是窗口更新左边界的情况
#       当然也要需要dp[i+1][j']的信息，可以通过w计算 k然后通过r拿到j'也可以，但是较为麻烦，不如直接存储
#       所以直接存储dp[i+1][j']-k'w然后+kw可以dp[i+1][j]的一个可以选择的值
#       窗口+元素有了，维护单调队列的单调性有了，只差窗口缩减了
#       由于我们存放dp[i+1][j']-k'w, 那只能通过当前的j,k计算出j',k'了
#               k' == k-c-1为过期的左边界
#               j' == (k') * v + r 为过期的
#   note：不可以只存储dp[i+1][j']-k'w，因为在q[0] == dp[i+1][expired_j] + (expired_k) * v
#       是比较的值有可能不是过期的元素，但因为值相同所以被移除了队列
#       所以窗口至少得存储k,或j
def h(V, W, C, X):
    n = len(V)
    dp = [[0] * (X + 1) for _ in range(n + 1)]

    for i in range(n - 1, -1, -1):  # 1)
        v, w, c = V[i], W[i], C[i]
        for r in range(min(X + 1, v)):     # 2) r 0,1,2,...,v-1
            q = deque()
            # for j in range(r, X + 1, v):    # 2)  4) 每回+v也就是 t+=1 每回选择了一个t
            #     k = j // v                  # 3), 当前是k，对于后边的来说他是k'
            j = r
            for k in range((X-r)//v + 1):    # 2)  4) 每回+v也就是 t+=1 每回选择了一个t
                # j = r + k * v                  # 3), 当前是k，对于后边的来说他是k'
                val = dp[i+1][j] - k * w
                while q and q[-1][1] <= val:
                    q.pop()
                q.append((k, val))
                expired_k = k-c-1
                if q[0][0] == expired_k:     # 6) 确保k'的取值范围
                    q.popleft()
                dp[i][j] = q[0][1] + k * w
                j += v      # 多种表示k,j的写法
    # print(dp)
    return dp[0][X]

def functional_test():
    V = [4, 1, 3, 2]
    W = [4, 2, 2, 4]
    C = [1, 3, 2, 1]
    X = 9
    print(f(V, W, C, X))
    print(g(V, W, C, X))
    print(h(V, W, C, X))


# for test
if __name__ == '__main__':
    # functional_test()
    # exit(0)
    n = 50
    n_epoch = 1000
    for epoch in range(n_epoch):
        V = np.random.randint(1, 10, n)
        W = np.random.randint(1, 10, n)
        C = np.random.randint(1, 10, n)
        X = np.random.randint(1, min(sum(V) >> 1, 1000))
        r1 = f(V, W, C, X)
        r2 = g(V, W, C, X)
        r3 = h(V, W, C, X)
        # print(r1, r2, r3)
        if not (r1 == r2 == r3):
            print(f'oops!!!, r1:{r1}, r2:{r2}, r3:{r3}')
            print(f'V = [{", ".join([str(v) for v in V])}]')
            print(f'W = [{", ".join([str(w) for w in W])}]')
            print(f'C = [{", ".join([str(c) for c in C])}]')
            print(f'X = {X}')
            break
    print("测试结束")

